#include "geometry.h"
#include "left_turn.h"
#include <algorithm>

namespace
{
   int find_min_point(const std::vector<point> &points)
   {
      int min = 0;
      for (unsigned int i = 1; i < points.size(); i++)
      {
         if (points.at(min).y > points.at(i).y || 
            points.at(min).y == points.at(i).y && points.at(min).x > points.at(i).x)
         {
            min = i;
         }
      }
      return min;
   }

   point zero = point(0, 0);

   int compare(const void * b1, const void * c1) 
   {
      point b = *(point*)b1;
      point c = *(point*)c1;
      int cmp = left_turn(b, zero, c);
      if (cmp != 0) 
      {
         return cmp;
      }
      if (b.y < c.y) 
      {
         return -1;
      }
      if (b.y > c.y) 
      {
         return 1;
      }
      if (b.x < c.x)
      {
         return -1;
      }
      if (b.x > c.x)
      {
         return 1;
      }
      return 0;
   }
}


void point_sort(std::vector<point> &points)
{
   point * arr = new point[points.size()];
   int n = points.size();
   for (int i = 0;  i < n; i++)
   {
      arr[i] = points[i];
   }
   
   int min = find_min_point(points);
   zero = points.at(min);
  
   std::qsort(arr, points.size(), sizeof(point), compare);
 
   points.clear();
   for (int i = 0;  i < n; i++)
   {
      points.push_back(arr[i]);
   }
   delete[] arr;
}

bool operator==(point a, point b)
{
   return (a.x == b.x) && (a.y == b.y);
}